package _01_排序;

import _01_排序.tools.Integers;
import _01_排序.tools.Times;

/*
    ◼ 执行流程（本课程统一以升序为例子）
    ① 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置
    ✓ 执行完一轮后，最末尾那个元素就是最大的元素
    ② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①，直到全部元素有序
    时间复杂度:最坏/平均时间复杂度：O(n^2),最好:O(n),只需要一趟扫描
    空间复杂度:O(1),不需要开辟新的空间
    稳定的排序算法

 */
public class BubbleSort01<E extends Comparable<E>> extends Sort<E>{

    //最终优化版
    @Override
    protected void sort() {
        for(int end = array.length-1;end>0;end--){
            //每一趟比较的索引,初始值赋值为1，如果数组是完全有序的，那么第一趟比较后就会提前结束循环
            int sortedIndex = 1;
            for(int begin=1;begin<=end;begin++){
                if(cmp(begin,begin-1)<0){
                    swap(begin,begin-1);
                    sortedIndex = begin; //只要进行交换，就记录最后一次交换的索引位置
                }
            }
            //这一趟循环结束后，下一次的范围就是0-sortedIndex
            end = sortedIndex;
        }
    }

    //无优化版
    public static void bubbleSort01(Integer[] array){
        for(int end = array.length-1;end>0;end--){
            for(int begin = 1;begin<=end;begin++){
                if(array[begin] < array[begin-1]){
                    int tmp = array[begin-1];
                    array[begin-1] = array[begin];
                    array[begin] = tmp;
                }
            }
        }
    }

    //判断数组是否已经有序，提前结束
    public static void bubbleSort02(Integer[] array){
        for(int end = array.length-1;end>0;end--){
            boolean sorted = true; //假定每次排序前是有序的
            for(int begin=1;begin<=end;begin++){
                if(array[begin]<array[begin-1]){
                    int tmp = array[begin-1];
                    array[begin-1] = array[begin];
                    array[begin] = tmp;
                    sorted = false; //修改状态,不是有序的
                }
            }
            //一趟排序过后
            if(sorted) break;
        }
    }

    //记录每一趟比较过后的索引，将大的比较范围缩小
    public static void bubbleSort03(Integer[] array){
       for(int end = array.length-1;end>0;--end){
           int sortedIndex = 1;
           for(int begin = 1;begin<=end;++begin){
               if(array[begin]<array[begin-1]){
                   int tmp = array[begin];
                   array[begin] = array[begin-1];
                   array[begin-1] = tmp;
                   sortedIndex = begin;
               }
           }
           end = sortedIndex;
       }
    }

    public static void main(String[] args) {
        Integer[] array1 = Integers.tailAscOrder(1,10000,2000);
        Integer[] array2 = Integers.copy(array1);
        Integer[] array3 = Integers.copy(array1);

        Times.test("bubbleSort01", ()->{
            bubbleSort01(array1);
        });

        Times.test("bubbleSort02", ()->{
            bubbleSort02(array2);
        });
        Times.test("bubbleSort03", ()->{
            bubbleSort03(array3);
        });
    }

}
